#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */

void level_order(struct Node* root)
{
    struct Node* phead = NULL;
    struct Node* proot = root;
    struct Node* ptail = NULL;
    do
    {
        root = proot;
        ptail = proot->left;
        if (ptail == NULL)
            ptail = proot->right;
        phead = ptail;
        proot = proot->next;
    } while (ptail == NULL && proot != NULL);

    if (phead == NULL)
        return;

    proot = root;
    struct Node* pnext = proot->left;
    while (proot != NULL)
    {
        pnext = proot->left;
        if (pnext != NULL)
        {
            ptail->next = pnext;
            ptail = ptail->next;
        }
        pnext = proot->right;
        if (pnext != NULL)
        {
            ptail->next = pnext;
            ptail = ptail->next;
        }
        proot = proot->next;
    }
    ptail->next = NULL;
    level_order(phead);
    return;
}

struct Node* connect(struct Node* root) {
    if (root == NULL)
        return root;
    level_order(root);
    return root;
}